//反转一个单链表。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 进阶: 
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
// Related Topics 链表

package leetcode.editor.cn;

public class ReverseLinkedList {
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedList().new Solution();
        ListNode node = ListNodeUtil.constructList(new int[]{1,2,3,4, 5});
        ListNode listNode = solution.reverseList(node);
        ListNodeUtil.printList(listNode);

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {

        /**
         * 1. 保存当前节点的next；
         * 2  当前节点的next指向新的head
         * 3. 把自己变成head
         * 3. 把自己变成第一步保存的节点
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {

            ListNode newHead = null;
            ListNode current = head;
            ListNode temp = null;
            while (current != null) {
                temp = current.next;
                current.next = newHead;
                newHead = current;
                current = temp;
            }

            return newHead;
        }

    }


//leetcode submit region end(Prohibit modification and deletion)

}